#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> res(nums.size() - k + 1);
        priority_queue<int, vector<int>, less<int>> q;
        unordered_map<int, int> m;
        for (int i = 0; i < k - 1; i++)
        {
            if (m.find(nums[i]) == m.end())
            {
                q.push(nums[i]);
            }
            m[nums[i]] += 1;
        }
        for (int i = 0; i < res.size(); i++)
        {
            // add next
            if (m.find(nums[i + k - 1]) == m.end())
            {
                q.push(nums[i + k - 1]);
                m[nums[i + k - 1]] = 1;
            }
            else
                m[nums[i + k - 1]] += 1;

            while (m.find(q.top()) == m.end())
                q.pop();
            res[i] = q.top();

            // remove first
            if (m[nums[i]] == 1)
                m.erase(nums[i]);
            else
                m[nums[i]] -= 1;
        }
        return res;
    }
};

int main()
{
    cout << "Code239" << endl;
    Solution s;
    vector<int> nums = {1, -1};
    vector<int> res = s.maxSlidingWindow(nums, 1);
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }
    return 0;
}